嗯。
字符串哈希太好用了你知道吗。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
由于一些基础字符串哈希算法在提高级别字符串算法已经不适用（例如字符串拼接，只能返回哈希值，不适合用于提高算法），本创作计划将分为“基础篇”与“提高篇”。
如果你对基础字符串哈希算法十分了解，请前往提高篇。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
字符串哈希是一种简单、用处广泛的字符串算法，可以处理大部分字符串问题。
首先我们要知道字符串哈希的原理是什么。
其实就是把一个字符串通过乘法压缩成一个数值。这个数值就叫哈希值。
例如定义 kkk 为乘数，长度为 555 的字符串 SSS 就可以压缩成 h(S)=S1×k4+S2×k3+S3×k2+S4×k1+S5×k0h(S)=S_1\times k^4+S_2\times k^3+S_3\times k^2+S_4\times k^1+S_5\times k^0h(S)=S1 ×k4+S2 ×k3+S3 ×k2+S4 ×k1+S5 ×k0。
这样我们就可以递推出 SSS 所有前缀的哈希值：h([S1,S2,...,Si])=k×h([S1,S2,...,Si−1])+Sih([S_1,S_2,...,S_i])=k\times h([S_1,S_2,...,S_{i-1}])+S_ih([S1 ,S2 ,...,Si ])=k×h([S1 ,S2 ,...,Si−1 ])+Si 。
这样，每个字符串都有一个对应的哈希值，不同的串哈希值也不同。
但这样数值是指数级增长的，到了后面 unsigned long long 都存不下，怎么办？
我们可以对哈希值对一个大数取模，这样虽然可能有两个不同字符串的哈希值相同，但错误率极小，如果模数是 ppp，则两个不同的随机字符串哈希值相同的概率为 1p\frac{1}{p}p1 （一般单模哈希的 ppp 不能取太小，因为根据生日悖论，p\sqrt pp 个随机字符串就很大概率出现一对哈希值相同的）。特别地，可以使用 unsigned long long 自然溢出，这可以看做模数 p=264p=2^{64}p=264。
求一个字符串哈希代码如下（自然溢出，乘数 k=131k=131k=131）：
时间复杂度：O(n)O(n)O(n)。
字符串哈希可以干什么呢？你可以看看下面的内容。（吓哭了）
判断两字符串是否相等
> 题目
> 给定两个长度为 nnn 的字符串 A,BA,BA,B，判断这两个字符串是否相等。
> 即判断是否对于所有 1≤i≤n1\le i\le n1≤i≤n，满足 Ai=BiA_i=B_iAi =Bi 。
这个简单，判断哈希值是否相等即可。
求哈希值时间复杂度：O(n)O(n)O(n)。
判断相等时间复杂度：O(1)O(1)O(1)。
字符串拼接
> 题目
> 给定两个字符串 A,BA,BA,B，请输出他们的哈希值和拼接后的哈希值。
假设需要拼接两个字符串 A,BA,BA,B，它们的长度分别为 n,mn,mn,m。
则它们的哈希值分别为 h(A)=A1×kn−1+A2×kn−2+...+An×k0h(A)=A_1\times k^{n-1}+A_2\times k^{n-2}+...+A_n\times k^0h(A)=A1 ×kn−1+A2 ×kn−2+...+An ×k0，h(B)=B1×km−1+B2×km−2+...+Bm×k0h(B)=B_1\times k^{m-1}+B_2\times k^{m-2}+...+B_m\times k^0h(B)=B1 ×km−1+B2 ×km−2+...+Bm ×k0。
假设拼接后的字符串 C=A+BC=A+BC=A+B。则有哈希值 h(C)=A1×kn+m−1+A2×n+m−2+...+An×km+B1×km−1+B2×km−2+...+Bm×k0=h(A)×km+h(B)h(C)=A_1\times k^{n+m-1}+A_2\times^{n+m-2}+...+A_n\times k^{m}+B_1\times k^{m-1}+B_2\times k^{m-2}+...+B_m\times k^0=h(A)\times k^m+h(B)h(C)=A1 ×kn+m−1+A2 ×n+m−2+...+An ×km+B1 ×km−1+B2
×km−2+...+Bm ×k0=h(A)×km+h(B)。
预处理 kik^iki 即可。
预处理，求哈希值时间复杂度：O(n+m)O(n+m)O(n+m)。
拼接时间复杂度：O(1)O(1)O(1)。
截取字符串一个子串
> 题目
> 给定一个字符串 AAA，给出 qqq 次询问，首先输出 AAA 的哈希值，然后输出每次询问查找的子串的哈希值。
我们可以按照上面的方法，先预处理出这个字符串的前缀哈希值。
下面的代码就是记录一个字符串的前缀哈希值：
记要截取的子串为 S′=[Sl,Sl****l+2,...,Sl+len−1]S'=[S_l,S_{l+1},S_{l+2},...,S_{l+len-1}]S′=[Sl ,Sl+1 ,Sl+2 ,...,Sl+len−1 ]。
则 h(S′)=Sl×klen−1+Sl+1×klen2+...+Sl+len−1×k0=(S1×kl+len−2+S2×kl+len−3+...+Sl+len−1×k0)−(S1×kl+len−2+S2×kl+len−3+...+Sl−1×klen)=h([S1,S2,...,Sl+len−1])−klenh([S1,S2,...,Sl−1])h(S')\\ =S_l\times k^{len-1}+S_{l+1}\times k^{len2}+...+S_{l+len-1}\times k^0\\ =(S_1\times k^{l+len-2}+S_2\times
k^{l+len-3}+...+S_{l+len-1}\times k^0)-(S_1\times k^{l+len-2}+S_2\times k^{l+len-3}+...+S_{l-1}\times k^{len})\\ =h([S_1,S_2,...,S_{l+len-1}])-k^{len}h([S_1,S_2,...,S_{l-1}])h(S′)=Sl ×klen−1+Sl+1 ×klen2+...+Sl+len−1 ×k0=(S1 ×kl+len−2+S2 ×kl+len−3+...+Sl+len−1 ×k0)−(S1 ×kl+len−2+S2 ×kl+len−3+...+Sl−1
×klen)=h([S1 ,S2 ,...,Sl+len−1 ])−klenh([S1 ,S2 ,...,Sl−1 ])。
预处理时间复杂度：O(n)O(n)O(n)
查询时间复杂度：O(q)O(q)O(q)
